简化路径
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：
1
2
3
| 输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
|
示例 2：
1
2
3
| 输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
|
示例 3：
1
2
3
| 输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
|
示例 4：
1
2
| 输入："/a/./b/../../c/"
输出："/c"
|
示例 5：
1
2
| 输入："/a/../../b/../c//.//"
输出："/c"
|
示例 6：
1
2
| 输入："/a//b////c/d//././/.."
输出："/a/b/c"
|
新的收获：
- Stack类的foreach写法居然是从栈底开始遍历的，并不是从栈顶往下走的，查看源码发现Stack继承Vector类，内部为一个数组，故使用foreach语句时被当做了一个数组来遍历。
- foreach写法确实是语法糖，但是在性能上，foreach居然要比for i++的写法要慢。
- 有点意料之外，根据第3 4次提交foreach居然执行效率还快一些，有可能是因为两个foreach遍历的都是一系数组，看网上有一些说，foreach在遍历链表时会慢很多。（也有可能只是偶然，我没有跑很多次对比）。
- replaceAll等、split这种复合运算的，都需要遍历整个数组，对时间的影响比较大，不能因为方便就用。
代码：
第一次提交（11%时）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public String simplifyPath(String path) {
if(path==null||path.length()==0)return null;
Stack<String> stack=new Stack<>();
String[] strs=path.replaceAll("/+","/").split("/");
for(String v:strs)
{
if(v.length()==0||v.equals("."))
continue;
if(v.equals(".."))
{
//一个是顶部没东西
if(stack.isEmpty())
continue;
//一个是顶部还有东西，取出
else {
stack.pop();
}
}else{
stack.add(v);
}
}
StringBuffer sb=new StringBuffer();
//如果没有东西，直接返回根目录就可以了
if(stack.empty())return "/";
//这里发现了个新的知识点呀，Stack类的foreach写法居然是从栈底开始遍历的，并不是从栈顶往下走的
//查看源码发现Stack继承Vector类，内部为一个数组，故使用foreach语句时被当做了一个数组来遍历。
for(String v:stack)
{
sb.append('/');
sb.append(v);
//sb.insert(0,v);
}
return sb.toString();
}
}
|
第二次提交(修改了foreach写法，发现提升不大，而且空间排少的代码也有使用foreach的)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public String simplifyPath(String path) {
if(path==null||path.length()==0)return null;
Stack<String> stack=new Stack<>();
String[] strs=path.replaceAll("/+","/").split("/");
for(int i=0;i< strs.length;i++)
{
if(strs[i].length()==0||strs[i].equals("."))
continue;
if(strs[i].equals(".."))
{
//一个是顶部没东西
if(stack.isEmpty())
continue;
//一个是顶部还有东西，取出
else {
stack.pop();
}
}else{
stack.push(strs[i]);
}
}
StringBuffer sb=new StringBuffer();
//如果没有东西，直接返回根目录就可以了
if(stack.empty())return "/";
for(int i=0;i<stack.size();i++)
{
sb.append('/');
sb.append(stack.get(i));
//sb.insert(0,v);
}
return sb.toString();
}
}
|
第三次提交（73%时，97%空）：
状态：通过
执行用时: 6 ms
内存消耗: 38.6 MB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public String simplifyPath(String path) {
if(path==null||path.length()==0)return null;
Stack<String> stack=new Stack<>();
String[] strs=path.split("/");
for(int i=0;i< strs.length;i++)
{
if(strs[i].length()==0||strs[i].equals("."))
continue;
if(strs[i].equals(".."))
{
//一个是顶部没东西
if(stack.isEmpty())
continue;
//一个是顶部还有东西，取出
else {
stack.pop();
}
}else{
stack.push(strs[i]);
}
}
//如果没有东西，直接返回根目录就可以了
if(stack.empty())return "/";
StringBuffer sb=new StringBuffer();
for(int i=0;i<stack.size();i++)
{
sb.append('/');
sb.append(stack.get(i));
//sb.insert(0,v);
}
return sb.toString();
}
}
|
在第三次基础上改回foreach，看一下时空的影响（91%时，88%空）：
执行用时: 5 ms
内存消耗: 38.7 MB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| class Solution {
public String simplifyPath(String path) {
if(path==null||path.length()==0)return null;
Stack<String> stack=new Stack<>();
String[] strs=path.split("/");
for(String v:strs)
{
if(v.length()==0||v.equals("."))
continue;
if(v.equals(".."))
{
//一个是顶部没东西
if(stack.isEmpty())
continue;
//一个是顶部还有东西，取出
else {
stack.pop();
}
}else{
stack.add(v);
}
}
//如果没有东西，直接返回根目录就可以了
if(stack.empty())return "/";
StringBuffer sb=new StringBuffer();
for(String v:stack)
{
sb.append('/');
sb.append(v);
}
return sb.toString();
}
}
|
